package tree;

import java.util.Scanner;


/**孩子-兄弟表示法建立树,并输出任一种遍历序列检查所建树的正确性
 * */
public class ChildrenBrother<AnyType> {
	public CBNode<AnyType> rootNode=null;
	public int i=0;
	
	public CBNode<AnyType> createTreeByChildAndBrother(AnyType[] preOrder){
		CBNode<AnyType> rootNode=null;
		if(i>=preOrder.length){
			throw new  ArrayIndexOutOfBoundsException();
		}
		AnyType data=preOrder[i++];
		if(data!=null){
			rootNode=new CBNode<AnyType>(data);
			rootNode.setChild(createTreeByChildAndBrother(preOrder));
			rootNode.setBrother(createTreeByChildAndBrother(preOrder));
		}
		return rootNode;
	}
	
	/**先序遍历*/
	public void preOrder(CBNode<AnyType> t){
		if(t!=null){
			/**访问根节点*/
			System.out.println(t.getData());
			/**遍历左子树*/
			preOrder(t.getChildren());
			/**遍历右子树*/
			preOrder(t.getBrother());
		}
	}
	
	

	public static void main(String[] args) {
		ChildrenBrother<Character> cb=new ChildrenBrother<Character>();
		Scanner in=new Scanner(System.in);
		System.out.println("请输入字符串，以先序的顺序创建创建二叉树：");
		//供测试数字串 :ABDH I  EJ K   CFL MP Q R    GN    
		String str=in.nextLine();
		/**将字符串转换成字符数组*/
		char[] tree=str.toCharArray();
		/**创建包装类的数组*/
		Character[] preOrder = new Character[tree.length];
		/**遍历数组，景数组中非空格的字符包装后，存入包装类数组，对空格字符赋值为null*/
		for(int i=0;i<tree.length;i++){
			if(tree[i]==' '){
				preOrder[i]=null;
			}else{
//				preOrder[i]=new Character(tree[i]);
				preOrder[i]=tree[i];
			}
		}
		cb.rootNode=cb.createTreeByChildAndBrother(preOrder);
		
		
		cb.preOrder(cb.rootNode);
		
		
	}


}

class CBNode<AnyType>{
	private AnyType data;
	private CBNode<AnyType> children;
	private CBNode<AnyType> brother;
	CBNode() {
		data=null;
		children=brother=null;
	}
	CBNode(AnyType data){
		this.data=data;
		children=brother=null;
	}
	CBNode(AnyType data,CBNode<AnyType> children,CBNode<AnyType> brother){
		this.data=data;
		this.children=children;
		this.brother=brother;
	}
	public  CBNode<AnyType> getChildren(){
		return children;
	}
	public void setChild(CBNode<AnyType> children){
		this.children=children;
	}
	public CBNode<AnyType> getBrother(){
		return brother;
	}
	public void setBrother(CBNode<AnyType> brother){
		this.brother=brother;
	}
	public Object getData(){
		return data;
	}
	public void setData(AnyType d){
		this.data=d;
	}
}
